The communications industry is rapidly changing to adjust to emerging technologies and ever increasing customer demand. This customer demand for new applications and increased performance of existing applications is driving communications network and system providers to employ networks and systems having greater speed and capacity (e.g., greater bandwidth). In trying to achieve these goals, a common approach taken by many communications providers is to use packet switching technology. Increasingly, public and private communications networks are being built and expanded using various packet technologies, such as Internet Protocol (IP).
A network device, such as a switch or router, typically receives, processes, and forwards or discards a packet based on one or more criteria, including the type of protocol used by the packet, addresses of the packet (e.g., source, destination, group), and type or quality of service requested. Packet forwarding decisions and other packet operations are demanding parts of switch and router design. For example, IP forwarding requires a longest prefix match. In order to support large number of layer 3 prefixes (e.g., IP, IPX), four to eight ternary content-addressable memory (TCAM) chips are often used due to the number of addresses that need to be supported. A longest prefix match is determined by performing a lookup operation on each of the TCAM chips. However, CAMs and TCAMs are expensive in terms of financial cost, power consumption and heat dissipation, and thus desired are new methods and apparatus for performing lookup operations.
Certain routers or other switching systems use a distributed routing technique in which line cards store routing information and are attached to an interconnection network for communicating packets between line cards. In a known system, each line card stores the full routing space, which typically requires several TCAMs. In another known system, a line card does not maintain the full routing space, but rather caches a few last used fully expanded addresses (e.g., no prefixes), and if the desired address does not exactly match the lookup value (e.g., destination address), a lookup request is forwarded to a supervisor card which performs the routing lookup operation and returns a routing response based on which the packet is routed by the line card. However, this caching is limited to fully expanded addresses as a routing lookup operation requires the result to be guaranteed to be that of a longest prefix match. By storing only fully expanded addresses, the search guarantees this, but it also causes many routing lookup operation misses causing a large number of routing requests to be sent to a supervisor line card which maintains the full routing space. Needed are new ways to more efficiently determine routing information.